#include <iostream>
#include <vector>

using namespace std;

//为什么想到用快慢指针做？
//因为这题满足“原地操作+筛选条件+保持顺序”三大特征，最优解法就是双指针

class Solution 
{
public:
	void moveZeroes(vector<int>& nums) 
	{
		int slow = 0;		//慢指针slow记录非0元素的存储位置的下一个位置
		//快指针fast遍历数组
		
		for (size_t fast = 0; fast < nums.size(); fast++) 
		{
			if (nums[fast] != 0) 
			{
				nums[slow] = nums[fast];
				slow++;
			}
		}
		
		// 把剩下的位置填 0，[slow...nums.size()-1]
		for (size_t i = slow; i < nums.size(); i++) 
		{
			nums[i] = 0;
		}
	}
};	

int main() 
{
	Solution sol;
	vector<int> nums = {0, 1, 0, 3, 12};
	
	sol.moveZeroes(nums);
	
	cout << "移动后的数组: ";
	for (size_t i = 0; i < nums.size(); i++) 
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	
	return 0;
}

